#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <memory>
#include <stack>

using namespace std;

//int firstUniqChar(string s) { //leetcode
//    map<char, int> m;
//    for (int i = 0; i < s.length(); ++i) {
//        if (m.count(s[i] >= 1)) {
//            map<char, int>::iterator iter = m.find(i + 1);
//            cout << iter->first << endl;
//        } else {
//            m.insert(pair<char, int>(s[i], 1));
//        }
//    }
//    map<char, int>::iterator iter;
//    for (int i = 1; i < m.size(); ++i) {
//        iter = m.find(i);
//        cout << iter->first << ',' << iter->second << endl;
//
//    }
//    return -1;
//}
//
//int judge(char c) {
//    if (c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
//        return 1;
//    }
//    return 0;
//}
//
//bool isPalindrome(string s) {
//    int i = 0;
//    int j = s.length() - 1;
//    if (s.length() == 1) {
//        return true;
//    }
//    transform(s.begin(), s.end(), s.begin(), ::tolower);
//    while (i < j) {
//        if (judge(s[i]) != 1) { //aaa
//            i++;
//        }
//        if (judge(s[j]) != 1) {
//            j--;
//        }
//        if (judge(s[i]) == 1 && judge(s[j]) == 1) { //要用大小写转换函数
//            if (s[i] != s[j]) {
//                return false;
//            }
//            i++;
//            j--;
//        }
//    }
//    if (i >= j)
//        return true;
//    else
//        return false;
//}
//
//int strStr(string haystack, string needle) {
//    if (needle == '') {
//        return 0;
//    }
//    if (haystack.length() < needle.length()) {
//        return -1;
//    }
//    int j;
//    int t;
//    for (int i = 0; i < haystack.length(); ++i) {
//        j = 0;
//        if (haystack[i] == needle[j]) {
//            j = 1;
//            t = i + 1;
//            while (j < needle.length()) {
//                if (haystack[t] != needle[j]) {
//                    break;
//                }
//                t++;
//                j++;
//            }
//            if (j == needle.length()) {
//                return i;
//            }
//        }
//    }
//    return -1;
//}
//
//void sort(string s) { //hgf gfh
//    int flag = 1;
//    int n = s.length() - 1;
//    while (n > 0 && flag == 1) {
//        flag = 0;
//        for (int i = 0; i < n; ++i) {
//            if (s[i] > s[i + 1]) {
//                flag = 1;
//                char t = s[i];
//                s[i] = s[i + 1];
//                s[i + 1] = t;
//            }
//        }
//        --n;
//    }
//    cout << s << endl;
//}

//bool isAnagram(string s, string t) {
//    if (s.length() != t.length()) {
//        return false;
//    }
//    int flag = 1;
//    int n = s.length() - 1;
//    while (n > 0 && flag == 1) {
//        flag = 0;
//        for (int i = 0; i < n; ++i) {
//            if (s{i} > s{i + 1}) {
//                flag = 1;
//                char k = s{i};
//                s{i} = s{i + 1};
//                s{i + 1} = k;
//            }
//        }
//        --n;
//    }
//
//    flag = 1;
//    int m = t.length() - 1;
//    while (m > 0 && flag == 1) {
//        flag = 0;
//        for (int i = 0; i < m; ++i) {
//            if (t{i} > t{i + 1}) {
//                flag = 1;
//                char k = t{i};
//                t{i} = t{i + 1};
//                t{i + 1} = k;
//            }
//        }
//        --m;
//    }
//    for (int i = 0; i < s.length(); ++i) {
//        if (s{i} != t{i}) {
//            return false;
//        }
//    }
//    return true;
//
//}
typedef struct node {
    int data;
    struct node *next;

    node(int d) : data(d), next(NULL) {}
} node;

//递归输出
void revise(node *head) {
    if (head == NULL) return;
    revise(head->next);
    printf("%d ", head->data);
}

void revise1(node *head) {
    if (!head)
        return;
    revise1(head->next);
    cout << head->data << " ";
}

bool isValidSudoku(vector<vector<char>> &board) {
    map<int, int> columns[9];
    map<int, int> rows[9];
    map<int, int> boxes[9];
    for (int i = 0; i < 9; ++i) { //行
        for (int j = 0; j < 9; ++j) { //列
            if (board[i][j] != '.') {
                int value = board[i][j] - '0';
                //cout << value << " ";
                if (columns[i].count(value) >= 1 || columns[j].count(value) >= 1 ||
                    columns[(i / 3) * 3 + j / 3].count(value) >= 1) {
                    cout << i << "," << j << "," << (i / 3) * 3 + j / 3 << endl;
                    return false;
                }
                columns[j].insert(pair<int, int>(value, 0));
                rows[i].insert(pair<int, int>(value, 0));
                boxes[(i / 3) * 3 + j / 3].insert(pair<int, int>(value, 0));
            }
        }
        cout << endl;
    }
    return true;
}

typedef struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
} TreeNode;

bool isSortBST(TreeNode *root) {
    stack<TreeNode *> stack; //定义栈  具有先进先出的功能
    long long inorder = (long long) INT_MIN - 1; //定义变量  假设为long范围的最小值
    while (!stack.empty() || root != NULL) { //当栈不为空或者结点不为空
        while (root != NULL) { //把当前结点的左子树和孩子结点左子树全部入栈  主要是为了符合中序遍历的特点(找到左子树最小的结点)
            stack.push(root); //入栈
            root = root->left;
        }
        root = stack.top(); //取栈顶元素
        stack.pop(); //栈顶元素出栈
        if (root->val <= inorder) { //每次判断当前结点的值是否小于等于前驱结点的值 如果是 直接返回false
            //正常情况下经过中序遍历后每个结点的值应该大于前驱结点的值
            return false;
        }
        inorder = root->val; //改变前驱结点的值 方便下一次判断
        root = root->right; //主要查看结点的右子树还有没有结点
    }
    return true;
}

void rotate(vector<vector<int>> &matrix) {
    //先转置  再翻转
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = 0; j <= i; ++j) {
            if (i != j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }


}

void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
    for (int i = m, j = 0; j < n; ++i, ++j) {
        nums1[i] = nums2[j];
    }
    int flag = 1;
    int len = nums1.size() - 1;
    while (len > 0 && flag == 1) {
        flag = 0;
        for (int i = 0; i < len; ++i) {
            if (nums1[i] > nums1[i + 1]) {
                flag = 1;
                int temp = nums1[i];
                nums1[i] = nums1[i + 1];
                nums1[i + 1] = temp;

            }
        }
        --len;
    }
    for (auto va : nums1) {
        cout << va << endl;
    }
}

void merge1(vector<int> &nums1, int m, vector<int> &nums2, int n) {
    int arr[nums1.size()];
    int i = 0, j = 0;
    int k = 0;
    while (i < m && j < n) {
        if (nums1[i] <= nums2[j]) {
            arr[k++] = nums1[i];
            ++i;
        } else {
            arr[k++] = nums2[j];
            ++j;
        }
    }
    if (j == n) {
        i = j;
    }
    while (i < m) {
        arr[k++] = nums1[i];
        ++i;
    }

    if (j == n) {
        while (i < m) {
            arr[k++] = nums1[i];
            ++i;
        }
    } else {
        while (j < n) {
            arr[k++] = nums2[j];
            ++j;
        }
    }
    for (int len = 0; len < k; ++len) {
        nums1[len] = arr[len];
    }

    for (auto va : nums1) {
        cout << va << endl;
    }
}
/**
 * 这个题目就是大数相乘，用数组存储的一个题目：
	核心思想就是：对于0到N，变量i是需要与数组的每一位都要相乘的，而且从低位开始相乘。
	对于数组中的每一位，它所存储的数是：（与i相乘+进位）%10。
	此外要注意：
		当你在计算的过程中，肯定要时时刻刻都清楚当前的数组真实的长度吧，
		所以在这里引进了变量k，当数组的最高位有进位时，就要根据进位去扩大数组了去存储了。
		当每一次乘以i时，变量n都需要重新赋值为0，因为相当于又从最低位0位开始新的一轮计算。
 * @param N
 */
//阶乘的升级版  15=1307674368000
void Print_Factorial(const int N) {
    int Num[3001] = {0};
    int i, j, k, n;
    k = 1;  //记录结果的位数
    n = 0;  //代表进位
    Num[0] = 1;
    int temp;
    for (i = 2; i <= N; ++i) {
        for (j = 0; j < k; ++j) {
            temp = i * Num[j] + n;
            Num[j] = temp % 10;
            n = temp / 10;
        }
        while (n != 0) {
            Num[k] = n % 10;
            k++;
            n = n / 10;
        }
    }
    for (int i = k - 1; i >= 0; --i) {
        printf("%d", Num[i]);
    }
}

void Print_add(const string a, const string b) {
    int arr[500] = {0};
    int i = a.length() - 1;
    int j = b.length() - 1;
    int n = 0; //表示进位
    int m = 0;
    while (i >= 0 && j >= 0) {
        int f1 = a[i] - '0';
        int f2 = b[j] - '0';
        int temp = f1 + f2 + n;
        arr[m++] = temp % 10;
        n = temp / 10;
        --i;
        --j;
    }
    if (i >= 0) {
        while (i >= 0) {
            int f2 = a[i] - '0' + n;
            arr[m++] = f2;
            --i;
        }

    } else if (j >= 0) {
        while (j >= 0) {
            int f2 = b[j] - '0' + n;
            arr[m++] = f2;
            --j;
        }
    }
    for (int k = m - 1; k >= 0; --k) {
        printf("%d", arr[k]);
    }

}
/**
 * 大数相乘
 * 先逆序  再相乘 进位
 *
 * @param a
 * @param b
 */
void Print_multi(const string a, const string b) {
    int arr[500] = {0};
    int fa[100] = {0};
    int fb[100] = {0};
    int k = 0;
    int m = 0;
    int n = 0;
    for (int i = a.length() - 1; i >= 0; --i) {
        fa[m++] = a[i] - '0';
    }
    for (int i = b.length() - 1; i >= 0; --i) {
        fb[n++] = b[i] - '0';
    }
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            arr[i + j] += fa[i] * fb[j];
        }
    }
    for (int k = 0; k < 499; ++k) {
        if (arr[k] >= 10) {
            arr[k + 1] += arr[k] / 10;
            arr[k] = arr[k] % 10;
        }
    }
    for (int k = 499; k >= 0; --k) {
        if (arr[k] != 0)
            printf("%d", arr[k]);
    }

}

int main() {
    Print_multi("429", "999");


    return 0;
}